Top K Numbers介紹大綱:
《上篇》
-介紹Binary Heap(二元堆積)的結構與特性
-Binary Heap與陣列的關係
《中篇》
-Binary Heap種類
-Heap Sort: 了解什麼是heapify，以及heapify如何利用binary heap實現陣列排序
《下篇》
-Top K Numbers Pattern介紹與應用題型

終於進入正題，如今天的文章標題，Top K Numbers就是把前面的Heap Sort所有招式貫穿起來，就能應付Top K Numbers的題型了!

Top K Numbers的題型有哪些?
通常這類型的題目中都有關鍵字"find the top / smallest / frequent K elements"(找出最大/最小/第k個元素)，只要出現這些關鍵字，就可以考慮使用Top K Numbers的技巧進行解題。

找出最大或最小元素，其實只需要使用min-heap(最小堆積)或max-heap(最大堆積)。
那麼，要應付找出第k大或的數字的題目，只要利用min-heap(最小堆積)+ hash map就可以完成題目。

我們先來回憶一下昨天提到的binary heap中每個節點位置之間的index關係:

• left child 的index 是2n + 1
• right child 的index是2n + 2
• parent 的 index是 (n-1)/2

對照昨天的heap sort的步驟，下面是heapify的程式碼:

class MaxHeap {    
    constructor() {        
        this.heap = [];    
    }    
    //將一個值插入heap中，並在插入後調整heap的結構，使其保持ax-heap(最大堆積)
    insert(val) {
        this.heap.push(val);
        this.heapifyUp();
    }  
    //在插入後，從heap底部開始向上調整heap結構，以維持max-heap(最大堆積)的屬性
    heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2); 
            if (this.heap[parentIndex] >= this.heap[index]) break;          
            [this.heap[parentIndex], this.heap[index]] = this.heap[index],this.heap[parentIndex]];
            index = parentIndex;
        }    
    }  
    //移除root(根節點)並返回heap中的最大值（即根節點），然後調整heap結構以保持max-heap(最大堆積)性質
    extractMax() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return max;
    }    
    //在移除最大值(即根節點)後，從根節點開始向下調整heap結構
    heapifyDown() {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];
        while (true) {
            let leftChildIndex = 2 * index + 1; 
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;
            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild > element) {
                    swap = leftChildIndex;
                }
            }
            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if ((swap === null && rightChild > element)
                     || (swap !== null && rightChild > leftChild)) {
                    swap = rightChildIndex;
                }
            }
            if (swap === null) break;
            this.heap[index] = this.heap[swap];
            this.heap[swap] = element;
            index = swap;
        }
    }
}

source:https://www.geeksforgeeks.org/javascript-program-to-find-top-k-elements/

其實在搜尋如何使用heap解決top frequent k elements這種題型時，發現其實使用bucket sort(桶子排序法)在時間複雜度上更有效率，且做法也更為簡潔有力= ="

不過沒關係，改天再來研究一下bucket sort的做法吧!
Good night!